package com.wrial.kind.dp;
/*
 * @Author  Wrial
 * @Date Created in 10:06 2020/8/13
 * @Description
 * 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
 * 输入: amount = 5, coins = [1, 2, 5]   输出: 4
 */

public class CoinChangeII {


    /**
     *  动态规划公式
     *  if i == coin dp[i]+1    dp[i]+=dp[i-coin]
     *  优化：给dp[0] 设置为1  if i>=coin dp[i] += dp[i-coin]
     *
     *  but，如果按照amount作为外层循环，那就会出现无效子问题
     *  比如amount=3 按照amount算得出结果为amount(2)+amount(1)
     *  然后account=5 amount(5)=amount(4)+amount(3)+1  但是在amount(4)中已经对amount(3)加过了
     *  这样就会导致重复
     *
     *  但如果使用的coin作为外层循环，变化特征如下
     *  0   1   2   3   4   5
     *  1   1   1   1   1   1   coin=1
     *  1   1   2   2   3   3   coin=2
     *  1   1   2   2   3   4   coin=5
     *  因此在解决最优子问题相加类型时，需要考虑是否会有重复条件出现，有重复就从小的范围作为外层循环
     *
     */
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = 1; i <= amount; i++) {

                if (i >= coin) {
                    dp[i] += dp[i - coin];
                }
            }
        }
        return dp[amount];
    }
}
